1. Field of the Invention
This invention is utilized for asynchronous transfer mode (hereinafter, "ATM") telecommunications. It relates to a telecommunications network and control system which, when a plurality of terminals which receive a best effort type service use the same route, the cell rates of the various terminals are controlled in such a manner that they rapidly approach values which are fair. This invention relates to rate control and traffic control in packet switching networks or ATM networks. It is provided in an ATM network and is utilized as a buffer means for temporarily storing cells or packets. This invention relates to techniques for controlling the prescribed intervals at which cells or packets are output to each connection. It also relates to congestion control, and in particular to the regulation of a cell rate and to the basis for cancelling this regulation. This invention also relates to techniques for setting up virtual paths (VPs) and virtual channels (VCs).
2. Background of Related Art
In a conventional best effort type service in an ATM network, in order to acquire information relating to congestion or acceptable bandwidth in a given route, cells for acquiring information (resource management cells: hereinafter, "RM cells") are sent back and forth between source and destination terminals, with the network writing information in these RM cells and the source-side terminals referring to this information and on this basis controlling their cell output rate.
For example, a service based on the available bit rate (ABR) protocol (See ATM Forum ATMF 95-0013R2), which is a typical best effort type service on an ATM network, is configured so that it begins by operating on the basis of the ABR protocol at all the nodes between the source and destination terminals, and at those terminals.
A prior art example of this will be explained with reference to FIG. 52-FIG. 57. FIG. 52 shows the overall constitution of a prior art ATM network. FIG. 53 shows the constitution of an RM cell. FIG. 54 and FIG. 55 are flowcharts showing the operation of a source-side terminal. FIG. 56 is a flowchart showing the operation of source-side and destination-side subscriber switches, and of a transit switch. FIG. 57 is a flowchart showing the operation of a destination-side terminal. The ATM network illustrated in FIG. 52 is constituted on the basis of the ABR protocol. In FIG. 52, numeral 20 and 40 represent switches which serve terminals, numeral 30 represents a transit switch, numeral 5 represents a transmission link, numeral 50-1 is a source-side terminal, and numeral 60-1 is a destination-side terminal. As shown in FIG. 53, an RM cell comprises an ATM header, a protocol identifier (ID), a direction identifier (DIR), a backward congestion notification (BN), a congestion indication (CI), a no-increase bit (NI) for prohibiting increase in the allowed cell rate, a request/acknowledgement (RA), the explicit rate (ER), the current allowed cell rate (CCR), the minimum cell rate (MCR), the queue length (QL), and the sequential number (SN).
RM cells are transmitted periodically between each pair of source and destination terminals. For example, source-side terminal 50-1 periodically outputs RM cells; transit switch 30 writes in these cells information relating to congestion in, or the acceptable bandwidth of, the route in question; and destination-side terminal 60-1 returns the cells. In this way, source-side terminal 50-1 is notified of whether there is congestion in that route.
According to the rules of the ABR protocol, source-side terminal 50-1 must transmit using a cell rate that does not exceed the allowed cell rate, termed the ACR.
When source-side terminal 50-1 receives a notification of congestion by means of an RM cell, it decreases the ACR on the basis of the ABR protocol. Conversely, when it has been notified that there is no congestion, it raises the ACR on the basis of the ABR protocol.
When one of the acceptable bandwidths of the network as notified by RM cells is the smallest, source-side terminal 50-1 changes to a cell rate that does not exceed whichever of this smallest value and the newly-computed ACR is the smaller. When the acceptable bandwidths of the network do not have a minimum value, source-side terminal 50-1 changes to a cell rate that does not exceed the ACR.
When a new virtual channel (VC) starts to transmit data, after it has transmitted an initial RM cell, it is allowed to transmit at a rate not exceeding the cell rate stipulated for the start of transmissions, which is called the initial cell rate (ICR).
After the initial RM cell has been returned, the cell rate is controlled by the same procedure as described above. FIG. 54 and FIG. 55 show the operation of source-side terminal 50-1 on the basis of an ABR protocol in the ATM network illustrated in FIG. 52. FIG. 56 shows the operation of switches 20, 30 and 40, and FIG. 57 shows the operation of destination-side terminal 60-1. As shown in FIG. 54, source-side terminal 50-1 generates an RM cell (S1), initializes this cell (S2) and outputs it (S3). The RM cell is returned by way of switch 20.fwdarw.switch 30.fwdarw.switch 40.fwdarw.destination-side terminal 60-1, whereupon it is received by source-side terminal 50-1 as shown in FIG. 55 (S11). If there is a congestion indication in the RM cell (S12), the ACR is decreased (S14), but if there is no congestion indication, the ACR is increased (S13). As a result, terminal 50-1 changes its cell output rate (S15).
As shown in FIG. 56, when switch 20, 30 or 40 receives an RM cell that has been output from source-side terminal 50-1 (S21), it writes an acceptable cell rate in the ER field (S22). If the switch has decided that there is congestion (S23), it writes a congestion indication in the CI field (S24). The switch then forwards the RM cell (S25).
As shown in FIG. 57, when destination-side terminal 60-1 receives an RM cell that has been output from source-side terminal 50-1 (S21), it writes an acceptable cell rate in the ER field (S22), and if it has decided that there is congestion (S23), it writes a congestion indication in the Cl field (S24). Destination-side terminal 60-1 then returns the RM cell (S26).
In conventional ABR, when congestion occurs due to a new terminal starting to transmit or to an increase in cell rate, and when notification is given of this congestion, each terminal that is notified decreases its cell rate, with the result that spare capacity is created. If notification is received that the congestion has been cleared, each terminal raises its cell rate again. Repeating this procedure constitutes a mechanism whereby a fair cell rate is gradually approached.
The control of cell rate will be further explained with reference to FIG. 58, which serves to explain cell rate control in an ATM network according to the prior art. It is assumed here that terminals 50-1 to 50-3 are sources and that connections 70-1, 70-2 and 70-3 are set up between these sources and respective destination terminals 60-1 to 60-3 via switches 20-40. These connections 70-1, 70-2 and 70-3 share transmission links 5 between switches 20-40. Cell rate control is performed as follows. Namely, source terminals 50-1 to 50-3 generate and insert management cells at fixed cell intervals, and send these management cells to destination terminals 60-1 to 60-3 and back again. Switches 20-40 write information in these cells and source terminals 50-1 to 50-3 refer to this information and on this basis perform cell rate control.
For example, a service based on the available bit rate (ABR) protocol (See ATM Forum ATMF 95-0013R2), which is a typical best effort type service on an ATM network, is configured so that it begins by operating on the basis of the ABR protocol at all the nodes between the source and destination terminals, and at those terminals.
A prior art example of this will be explained with reference to FIG. 52-FIG. 57. FIG. 52 shows the overall constitution of a prior art ATM network. FIG. 53 shows the constitution of an RM cell. FIG. 54 and FIG. 55 are flowcharts showing the operation of a source-side terminal. FIG. 56 is a flowchart showing the operation of source-side and destination-side subscriber switches, and of a transit switch. FIG. 57 is a flowchart showing the operation of a destination-side terminal. The ATM network illustrated in FIG. 52 is constituted on the basis of the ABR protocol. In FIG. 52, 20 and 40 represent switches which serve terminals, 30 represents a transit switch, 5 represents a transmission link, 50-1 is a source-side terminal, and 60-1 is a destination-side terminal. As shown in FIG. 53, an RM cell comprises an ATM header, a protocol identifier (ID), a direction identifier (DIR), a backward congestion notification (BN), a congestion indication (CI), a no-increase bit (NI) for prohibiting increase in the allowed cell rate, a request/acknowledgement (RA), the explicit rate (ER), the current allowed cell rate (CCR), the minimum cell rate (MCR), the queue length (QL), and the sequential number (SN).
RM cells are transmitted periodically between each pair of source and destination terminals. For example, source-side terminal 50-1 periodically outputs RM cells; transit switch 30 writes in these cells information relating to congestion in, or the acceptable bandwidth of, the route in question; and destination-side terminal 60-1 returns the cells. In this way, source-side terminal 50-1 is notified of whether there is congestion in that route.
According to the rules of the ABR protocol, source-side terminal 50-1 must transmit using a cell rate that does not exceed the allowed cell rate, termed the ACR.
When source-side terminal 50-1 receives a notification of congestion by means of an RM cell, it decreases the ACR on the basis of the ABR protocol. Conversely, when it has been notified that there is no congestion, it raises the ACR on the basis of the ABR protocol.
When one of the acceptable bandwidths of the network as notified by RM cells is the smallest, source-side terminal 50-1 changes to a cell rate that does not exceed whichever of this smallest value and the newly-computed ACR is the smaller. When the acceptable bandwidths of the network do not have a minimum value, source-side terminal 50-1 changes to a cell rate that does not exceed the ACR.
When a new virtual channel (VC) starts to transmit data, after it has transmitted an initial RM cell, it is allowed to transmit at a rate not exceeding the cell rate stipulated for the start of transmissions, which is called the initial cell rate (ICR).
After the initial RM cell has been returned, the cell rate is controlled by the same procedure as described above. FIG. 54 and FIG. 55 show the operation of source-side terminal 50-1 on the basis of an ABR protocol in the ATM network illustrated in FIG. 52. FIG. 56 shows the operation of switches 20, 30 and 40, and FIG. 57 shows the operation of destination-side terminal 60-1. As shown in FIG. 54, source-side terminal 50-1 generates an RM cell (S1), initializes this cell (S2) and outputs it (S3). The RM cell is returned by way of switch 20.fwdarw.switch 30.fwdarw.switch 40.fwdarw.destination-side terminal 60-1, whereupon it is received by source-side terminal 50-1 as shown in FIG. 55 (S11). If there is a congestion indication in the RM cell (S12), the ACR is decreased (S14), but if there is no congestion indication, the ACR is increased (S13). As a result, terminal 50-1 changes its cell output rate (S15).
As shown in FIG. 56, when switch 20, 30 or 40 receives an RM cell that has been output from source-side terminal 50-1 (S21), it writes an acceptable cell rate in the ER field (S22). If the switch has decided that there is congestion (S23), it writes a congestion indication in the CI field (S24). The switch then forwards the RM cell (S25).
As shown in FIG. 57, when destination-side terminal 60-1 receives an RM cell that has been output from source-side terminal 50-1 (S21), it writes an acceptable cell rate in the ER field (S22), and if it has decided that there is congestion (S23), it writes a congestion indication in the CI field (S24). Destination-side terminal 60-1 then returns the RM cell (S26).
In conventional ABR, when congestion occurs due to a new terminal starting to transmit or to an increase in cell rate, and when notification is given of this congestion, each terminal that is notified decreases its cell rate, with the result that spare capacity is created. If notification is received that the congestion has been cleared, each terminal raises its cell rate again. Repeating this procedure constitutes a mechanism whereby a fair cell rate is gradually approached.
The control of cell rate will be further explained with reference to FIG. 58, which serves to explain cell rate control in an ATM network according to the prior art. It is assumed here that terminals 50-1 to 50-3 are sources and that connections 70-1, 70-2 and 70-3 are set up between these sources and respective destination terminals 60-1 to 60-3 via switches 20-40. These connections 70-1, 70-2 and 70-3 share transmission links 5 between switches 20-40. Cell rate control is performed as follows. Namely, source terminals 50-1 to 50-3 generate and insert management cells at fixed cell intervals, and send these management cells to destination terminals 60-1 to 60-3 and back again. Switches 20-40 write information in these cells and source terminals 50-1 to 50-3 refer to this information and on this basis perform cell rate control.
For example, in the cell rate control used in the ABR protocol according to ATM Forum specifications (95-0013R2, 94-0983, 95-0195, etc.), in order to control the cell rate of each connection in accordance with the residual bandwidth and the requested bandwidth of a shared route in such manner that the cell rates are fair and congestion does not occur, the source terminals transmit management cells at fixed cell intervals and each switch through which these management cells pass reads the allowed cell rate of the terminals from the management cell and calculates (i) information relating to congestion relevant to the switch itself, and (ii) the acceptable cell rate. When a source terminal transmits, the maximum value which the allowed cell rate can have (i.e., the peak cell rate: PCR) in each connection is written in the management cells as the initial value of the acceptable cell rate. Only when the acceptable cell rate calculated by a switch is smaller than the acceptable cell rate written in a returned management cell does the switch write that calculated rate in the management cell and thereby notify the source terminal. The source terminal then sets its own ACR equal to or less than the notified acceptable cell rate, and proceeds to transmit cells at a rate not exceeding this ACR.
FIG. 59-FIG. 61 show the control flow at the switches. FIG. 59 shows the control when it has been decided that there is congestion. FIG. 60 shows the control when a management cell has arrived from a source-side terminal. FIG. 61 shows the control when a management cell is returning from a destination-side terminal. Each switch observes the queue length in the transmission queue cell buffer, and if the queue exceeds a threshold the switch decides that there is congestion at itself. If the queue does not exceed the threshold, the switch decides that there is no congestion. If the switch decides that there is congestion, then as shown in FIG. 59, it calculates the current allowed cell rate reduced by a fixed proportion and takes this as the acceptable cell rate at that switch.
This will now be explained with regard to the j.sup.th connection (j=1, 2, . . . , n). ERQ.sub.j is obtained by multiplying MACR.sub.j, which relates to this j.sup.th connection, by ERD, which is a constant that is less than 1 (S31). ERQ.sub.j is then taken as the acceptable cell rate (S32). When a management cell from a source terminal arrives, then as shown in FIG. 60 the current allowed cell rate written in that management cell is taken as ccr.sub.j (S41). Next, the value of: EQU ccr.sub.j .times.min(1, R.sub.0 /rate.sub.j)
is obtained and set as the new allowed cell rate ccr.sub.j, which is then used to obtain the value of: EQU MACR.sub.j +(ccr.sub.j -MACR.sub.j).times.AVF
which is set as the new MACR.sub.j (S42). Here, R.sub.0 and AVF are constants, and rate.sub.j is the actual cell rate obtained from the current observation of the j.sup.th connection. As shown in FIG. 61, when a returning management cell arrives at a switch, the switch refers to the field value ER.sub.c in the management cell, this value serving to give notification of the acceptable cell rate. If ERQ.sub.j &lt;ER.sub.c (S51), the switch replaces ER.sub.c in this management cell with ERQ.sub.j (S52). If ERQ.sub.j .gtoreq.ER.sub.c, the switch transfers this management cell towards the source terminal without modifying it (S53). Because the source terminal sets its ACR below the notified acceptable cell rate, its allowed cell rate (ACR) is decreased.
FIG. 62 shows the control flow at a switch when it has decided that there is no congestion. When a switch decides that there is no congestion, it makes its acceptable cell rate larger than the allowed cell rate. That is to say, it multiplies: EQU 1-rate.sub.j /R.sub.0
by a constant which will be termed "Gain", adds 1 to this product and takes the result as ERX.sub.j. It also takes the product of this and ERQ.sub.j as the new ERQ.sub.j ; takes the smallest of this ERQ.sub.j, MACR.sub.j .times.ERU, and R.sub.0, as the new ERQ.sub.j ; and takes the larger of this ERQ.sub.j and MACR.sub.j .times.ERD as the new ERQ.sub.j (S61). The same control procedure is applied whether the management cell has arrived from the source side or is being returned from the destination side, and the result of this control procedure is that the ACR of the source terminal increases.
Next, an explanation will be given of conventional usage/network parameter control (UPC/NPC). ATM transfers information through a network after splitting it up into fixed-length packets called cells, and manages traffic on the basis of cell interval. In order to manage traffic in this way, a cell interval is stipulated for each connection, and a utilization monitor such as UPC/NPC is generally installed in order to monitor compliance with this cell interval. UPC/NPC immediately discards or tags any cells which arrive at shorter intervals than the stipulated cell interval.
However, because cells are transmitted asynchronously in an ATM network, each cell may be subject to a different delay while being transferred through the network. As a result, even if a subscriber has output cells in compliance with the stipulated cell interval, it will sometimes be impossible to satisfy the prescribed cell interval at a point where UPC/NPC is implemented. Cell delay variation (CDV) is the term used to describe fluctuation in cell transfer delay, and this CDV creates problems for UPC/NPC and traffic management. It has been proposed that the occurrence of CDV in a network could be reduced by traffic shaping, which is a technique whereby, once cells have been stored in a cell buffer, they are read from the buffer in a controlled manner.
An ABR service which has been much discussed in recent years in the ATM Forum is one which performs flow control by employing RM cells to give end-to-end notification of residual bandwidth on a given route. In an ABR service, the control loop comprising RM cells is closed end-to-end and therefore even if RM cells are dropped due to congestion, a negative feedback mechanism operates to restrict the flow of cells. Nevertheless, if cell transfer delay becomes large, as can happen in a public network, the information obtained by the RM cells relating to residual bandwidth on a given route will already be out-of-date, with the resulting problem that it is impossible to obtain a good control effect.
In order to overcome this problem, studies have been made of deploying VD/VS (virtual destination/virtual source) for closing control loops by means of RM cells at suitable places in the public network. In VD/VS, cell buffers are provided and cells are stored for each connection. Reading of cells from the cell buffers is performed by traffic shaping. When an RM cell, output from a source-side switch, returns after having been transferred through the network, a cell transmission interval for the connection in question is decided on the basis of the contents of the RM cell, and cells for that connection are read from the cell buffer at this interval.
If a higher layer protocol than the cell transmission layer provides a retransmission function, then when cells are dropped in the network, the retransmission function will operate, with the result that the degree of congestion may increase. In order to prevent this sort of slide into catastrophically serious congestion, it is essential to regulate the volume of traffic entering the network when the network has become congested.
The following method has previously been proposed for this purpose. Namely, as found in Chaki, "An Examination of Cell Level Congestion Clearing Systems" (Preprints of the Switching Systems Technical Group of the IEICE Japan, SSE 94-97), it is proposed that the volume of traffic should be regulated by a fixed factor when congestion has occurred. According to this method, if congestion occurs, the volume of traffic is regulated by a prescribed factor, and if the congestion is not cleared within a prescribed time, continued attempts are made to overcome the congestion by progressively making the regulation factor more stringent. When the congestion is cleared, the regulation factor is successively relaxed and there is a shift to a normal state.
In multimedia communications implemented on an ATM network, the connections exhibit a wide range of peak rates and average rates. For this reason, the different peak rates and average rates are divided into what are called "call types", and the call admission control (CAC) is carried out so as to meet the requested call quality for each call type.
The symbols used in this specification will now be defined. r.sub.i and a.sub.i are respectively the peak rate and the average rate of call type i, and a.sub.all and C are respectively the sum of the average rates of all the VCs, and the VP bandwidth. CLR.sub.AVE is the average cell loss ratio for all call types.
Letting the cell rate probability density function for call type i be f.sub.i (x), and the cell rate probability density function for the other call types apart from call type i be F.sub.i (x), then the cell loss ratio for call type i, CLR.sub.i, can be obtained by as: ##EQU1## (see T. Murase, H. Suzuki, S. Sato and T. Takeuchi, "A call admission control scheme for ATM networks using a simple quality estimate". IEEE J. Select. Areas Commun., Vol.9 (No.9): pp.1461-1470, December 1991). In call admission control, a connection request is accepted if the largest of the cell loss ratios obtained for the different call types by means of Eq.1 satisfies a certain standard value.
FIG. 63 serves as a numerical example of the case where CAC is carried out with a stipulated value of 10.sup.-6 for cell loss ratio. It is assumed in FIG. 63 that call type 1 has peak rate r.sub.1 =10 Mb/s and average rate a.sub.1 =0.05 Mb/s, and that call type 2 has peak rate r.sub.2 =1.5 Mb/s and average rate a.sub.2 =0.15 Mb/s. FIG. 63 shows the cell loss ratio and the number of connections for each call type in a multiple access environment. The number of call type 1 connections is plotted along the horizontal axis, the number of call type 2 connection is plotted along the left-hand vertical axis, and cell loss ratio (CLR) is plotted along the right-hand vertical axis. From FIG. 63 it can be seen that:
1) Call type 1 has a higher cell loss ratio than call type 2. Under some circumstances there is more than an order of magnitude difference. PA0 2) Even though the average cell loss ratio is more than an order of magnitude lower than the stipulated value, the cell loss ratio of call type 1 approaches the stipulated value.
Thus, in an ATM network intended for multimedia communications, because the connections exhibit a wide range of cell rates, and because any notified information relating to residual bandwidth on a given route will be out-of-date if the distance to the terminals is large, it is difficult to obtain a good control effect. For example, the transmission of RM cells takes time, and it takes time for a newly-transmitting terminal to control the ACR of a terminal which is already transmitting. Consequently, it takes time to converge to a fair allocation of bandwidth. Adequate tracking of cell rate and network conditions is also difficult, since these change from moment to moment.
To shorten the time required to raise the ACR, the ICR of each terminal can be set on the high side, but this still leaves the problem that an appreciable amount of time is taken to notify a terminal of congestion if the distance to the terminal is large. Various measures are then required to deal with the problem of congestion, such as ensuring that long buffers are employed in the network and decreasing the network utilization.
Even if the distance to terminals is short, it still takes a certain amount of time to converge to a cell rate which is fair, and so there is a potential need to reduce this time.
In the prior art, the acceptable cell rates of connections routed through the same switch are increased or decreased on the basis of the same congestion situation. This amounts to control which performs a uniform operation, i.e. making a uniform increase or decrease in the ACRs, and this will not always be fair.
When traffic shaping is carried out, for example in the case of the VD/VS scheme described above, cell buffer queues will be more frequent when the number of connections increases, and the increased memory etc. needed to deal with this means that the hardware scale expands. In traffic shaping, only one cell can be transferred per slot, and if a plurality of cells are scheduled for the same slot, some of them will not be transferred. This becomes an actual rather than a potential problem if the number of connections increases, since then there is a high probability that a plurality of cells will be scheduled for the same slot.
When there is severe congestion, it takes time for the congestion to clear. Because the increase in traffic immediately after cell rate regulation has been cancelled is not taken into account when relaxing the regulation, repetitions of relaxation followed immediately by more severe regulation occur, and it takes time to move to a steady state.
When there are many call types, CAC has to be performed with an awareness of the cell loss ratio of each call type. If cell loss ratio is calculated rigorously in accordance with Eq.1, convolution will be necessary for each call type, and therefore in a multimedia environment where there are a large number of call types, the computational requirements will be very high.
Because CAC involves deciding whether or not to accept a connection request when that connection is being set up, a high degree of responsiveness is needed in order to offer a real-time switching service.
The present invention has been made in the light of this technical background. The various objects of this invention include the following to provide a dynamic rate control system whereby the cell rates of a plurality of terminals in a best effort type service can be controlled fairly; (2) to provide a dynamic rate control system capable of causing the cell rates of a plurality of terminals to converge rapidly to fair values; (3) to provide a dynamic rate control system whereby even when the distances to a plurality of terminals are large, the cell rate of each terminal can be controlled fairly without causing transmission delays; (4) to provide a dynamic rate control system capable of changing the bandwidth that can be utilized by each connection so that it becomes as large as possible, while ensuring that the acceptable cell rates notified to the various connections are fair; (5) to provide a dynamic rate control system capable of implementing traffic shaping by means of comparatively modest hardware even when there are a large number of connections; (6) to provide a dynamic rate control system capable of transferring a plurality of cells scheduled for the same slot (i.e., for the same time); (7) to provide a dynamic rate control system capable of increasing the throughput of an ATM network; (8) to provide a dynamic rate control system capable of clearing congestion rapidly; (9) to provide a dynamic rate control system capable of improving the responsiveness of the CAC by calculating the cell loss ratio for each call type by means of a simple calculation even when there are a large number of call types; (10) and to provide a dynamic rate control system capable of performing smooth call admission control.